class HashTable {
  constructor() {
    this.hashList = []
    this.limit = 7
    this.length = 0
  }

  hashFunc(key) {
    let hashCode = 0
    for (let i = 0; i < key.length; i++) {
      hashCode = 37 * hashCode + key.charCodeAt(i)
    }
    return hashCode % this.limit
  }

  // 插入或者修改
  put(key, value) {
    const index = this.hashFunc(key)

    let bucket = this.hashList[index]
    if (!bucket) {
      bucket = []
      this.hashList[index] = bucket
    }
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i]
      if (tuple[0] === key) {
        tuple[1] = value
        return
      }
    }

    bucket.push([key, value])
    this.length++
    if (this.limit * 0.75 < this.length) {
      // 扩容
      const newLimit = this.getPrime(Math.floor(this.limit * 2))
      this.resize(newLimit)
    }
  }

  // 获取
  get(key) {
    const index = this.hashFunc(key)
    const bucket = this.hashList[index]
    if (!bucket) return null
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i]
      if (tuple[0] === key) {
        return tuple[1]
      }
    }
    return null
  }

  // 删除
  remove(key) {
    const index = this.hashFunc(key)
    const bucket = this.hashList[index]
    if (!bucket) return -1
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i]
      if (tuple[0] === key) {
        bucket.splice(i, 1)
        this.length--
        if (this.length < this.limit * 0.25 && this.limit > 7) {
          // 减小
          const newLimit = this.getPrime(Math.floor(this.limit / 2))
          this.resize(newLimit)
        }
        return true
      }
    }
    return -1
  }

  // 是否为空
  isEmpty() {
    return this.length === 0
  }

  // 大小
  size() {
    return this.length
  }

  // 重新设置哈希表大小
  resize(newLimit) {
    const oldHashList = this.hashList
    this.hashList = []
    this.limit = newLimit
    this.length = 0

    oldHashList.forEach(bucket => {
      if (bucket) {
        bucket.forEach(tuple => {
          this.put(tuple[0], tuple[1])
        })
      }
    })
  }

  getPrime(num) {
    while (this.isPrime(num)) {
      // 是质数
      num++
    }
    return num
  }

  isPrime(num) {
    if (num <= 1) {
      return false
    }
    for (let i = 2; i <= Math.sqrt(num); i++) {
      if (num % i === 0) {
        return true
      }
    }
    return false
  }
}

const ht = new HashTable()


ht.put('class1', 'Tom')
ht.put('class2', 'Mary')
ht.put('class3', 'Gogo')
ht.put('class4', 'Tony')
ht.put('class5', '5')
ht.put('class6', '6')
ht.put('class7', '7')
ht.put('class8', '8')
ht.put('class9', '9')
ht.put('class10', '10')
console.log('11111111', ht.size());//10
console.log('22222222222', ht.limit);//17

ht.remove('class4')
ht.remove('class5')
ht.remove('class6')
ht.remove('class7')
ht.remove('class8')
ht.remove('class9')
ht.remove('class10')

console.log('11111111', ht.size());//10
console.log('22222222222', ht.limit);//17

console.log('99999999', ht.get('class2'));
